Edge simplification algorithms have been subject to an increased research interest with numerous improvements and enhancements in recent years.
On the geometry level, dense edge visualizations can be uncluttered by using Path Bundling techniques. They trade clutter for overdraw by routing geometrically and semantically related edges along similar paths. This improves readability in terms of finding groups of nodes related to each other by tracing groups of paths to form bundles, which are separated by whitespace as described by Gansner, E., Hu, Y., North, S., and Scheidegger, C. in “Multilevel agglomerative edge bundling for visualizing large graphs.” In Proc. PacificVis, pages 187-194. Meanwhile Dickerson et al. merge edges by reducing non-planar graphs to planar ones (Dickerson, M., Eppstein, D., Goodrich, M. T., and Meng, J. Y. (2003). Confluent Drawings: Visualizing Non-planar Diagrams in a PlanarWay. In Liotta, G., editor, Graph Drawing, number 2912 in Lecture Notes in Computer Science, pages 1-12. Springer Berlin Heidelberg.)
An early edge bundling technique was “flow map visualization”, which produces a binary clustering of nodes in a directed graph representing flows as described by Phan, D., Xiao, L., Yeh, R., Hanrahan, P., and Winograd, T. in “Flow map layout in Proceedings of the Proceedings of the 2005 IEEE Symposium on Information Visualization, INFOVIS '05, pages 29-. Washington, D.C., USA. IEEE Computer Society. The control meshes of maps are used by several authors to route curved edges, for example as described by Qu, H., Zhou, H., and Wu, Y. (2007). in “Controllable and Progressive Edge Clustering for Large Networks” published by Kaufmann, M. and Wagner, D., in Graph Drawing, number 4372, Lecture Notes in Computer Science, pages 399-404. Springer Berlin Heidelberg, or by Zhou, H., Yuan, X., Cui, W., Qu, H., and Chen, B. in “Energy-Based Hierarchical Edge Clustering of Graphs” published in Visualization Symposium, 2008. Pacific VIS '08. IEEE Pacific, pages 55-61. These techniques were later generalized into Edge Bundling approaches that use a graph structure to route curved edges. Holten pioneered this approach for compound graphs by routing edges along the hierarchy layout using B-splines in “Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data” IEEE TVCG, 12(5):741-748. Gansner and Koren bundled edges in a similar circular node layout by area optimization metrics in “Improved Circular Layouts” published in Kaufmann, M. and Wagner, D., editors, Graph Drawing, number 4372 in Lecture Notes in Computer Science, pages 386-398. Springer Berlin Heidelberg. Control meshes can also be used for edge clustering in graphs as described in the Qu et al and Zhou et al publications mentioned above. A Delaunay-based extension called Geometric-Based Edge Bundling (GBEdge Bundling) as described by Cui, W., Zhou, H., Qu, H., Wong, P. C., and Li, X. in “Geometry-Based Edge Clustering for Graph Visualization”, IEEE Transactions on Visualization and Computer Graphics, 14(6):1277-12841; and “Winding Roads” (WR) that use Voronoï diagrams for 2D and 3D layouts are also known, from Lambert, A., Bourqui, R., and Auber, D. in “3D edge bundling for geographical data visualization”, Proc. Information Visualisation, pages 329-335, and from Lambert, A., Bourqui, R., and Auber, D. “Winding roads: Routing edges into bundles” CGF, 29(3):432-439.
A popular technique is the Force-Directed edge layout technique which uses curved edges to minimize crossings, and implicitly creates bundle-like shapes, as described by Dwyer, T., Marriott, K., and Wybrow, M. in “Integrating edge routing into force-directed layout” Proc. Graph Drawing, pages 8-19. Force-Directed Edge Bundling (FDEdge Bundling) creates bundles by attracting control points on edges close to each other as described by Holten, D. and van Wijk, J. J. in “A user study on visualizing directed edges in graphs” Proc. ACM CHI, pages 2299-2308, and was adapted to separate bundles running in opposite directions by Selassie, D., Heller, B., and Heer, J. in “Divided edge bundling for directional network data. IEEE TVCG, 19(12):754-763 and Stark, H. and Woods, J. in “Probability, random processes, and estimation theory for engineers.” Prentice-Hall. The MINGLE method uses multilevel clustering to significantly accelerate the bundling process as presented by Gansner, E., Hu, Y., North, S., and Scheidegger, C. in “Multilevel agglomerative edge bundling for visualizing large graphs”, Visualization Symposium (PacificVis), 2011 IEEE Pacific, pages 187-194.
Computation times for larger graphs struggle with the algorithmic complexity of the Edge Bundling problem. This makes scalability a major issue when using the Edge Bundling techniques mentioned above. Accordingly, it remains desirable to provide a more computationally efficient, scalable, configurable and flexible approach to bundling operations.
It is also desirable to develop clearer representations of bundled paths.
It is also desirable to develop mechanisms for the generation of families of paths.